
/*
回溯
连接：https://leetcode.cn/problems/surrounded-regions/description/
题目：130. 被围绕的区域


    正难则反
        沿边界进行处理，碰到o之后修改矩阵情况，边界处理之后，内部的就是被包围的
  


   
    
*/
class Solution {
public:
    int dx[4] = {0,0,-1,1};
    int dy[4] = {-1,1,0,0};
    int m,n;
    void solve(vector<vector<char>>& board) {
        m = board.size();
        n = board[0].size();
        //修改边界
        for(int i=0;i<m;i++)
        {
            if(board[i][0]=='O')
                dfs(board,i,0);
            if(board[i][n-1]=='O')
                dfs(board,i,n-1);
        }
        for(int j=0;j<n;j++)
        {
            if(board[0][j]=='O')
                dfs(board,0,j);
            if(board[m-1][j]=='O')
                dfs(board,m-1,j);
        }
        //还原数组
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(board[i][j]=='.')
                    board[i][j] = 'O';
                else if(board[i][j]=='O')
                    board[i][j] = 'X';
            }
        }
    }
    void dfs(vector<vector<char>>& board,int i,int j)
    {
        board[i][j] = '.';
        for(int k=0;k<4;k++)
        {
            int x = dx[k]+i;
            int y = dy[k]+j;
            if(x>=0 && x<m && y>=0 && y<n && board[x][y] == 'O')
                dfs(board,x,y);
        }
    }
};